package com.leetcode.p0;

import com.bean.ListNode;
import com.utils.DataUtils;

public class Test86 {

    public ListNode partition(ListNode head, int x) {
        ListNode smallHead = new ListNode();
        ListNode curSmall = smallHead;

        ListNode bigHead = new ListNode();
        ListNode bigCur = bigHead;

        while (head != null) {
            if (head.val < x) {
                curSmall.next = head;
                curSmall = curSmall.next;
            } else {
                bigCur.next = head;
                bigCur = bigCur.next;
            }
            head = head.next;
        }

        bigCur.next = null;
        curSmall.next = bigHead.next;

        return smallHead.next;
    }

    public static void main(String[] args) {
        Test86 test = new Test86();
//        ListNode head = DataUtils.getListNode(new int[]{3, 11, 7, 4, 9, 4, 9, 6, 2, 99});
        ListNode head = DataUtils.getListNode(new int[]{1, 4, 3, 2, 5, 2});
//        ListNode head = DataUtils.getListNode(new int[]{3, 11, 7, 4});
        DataUtils.printListNode(test.partition(head, 3));
    }
}
